题解 CF441C@洛谷 | 441C@Codeforces 【Valera and Tubes 】

upd(2020.10.5)：修复一个手贱错误。

题意：一个 $m\times n$ 的网格图，每次连一条线，要求这条线：

• 至少包含两个点。
• 必须连续：也就是说，每一步可以继续向前画，也可以向左或向右转弯 $90\degree$。
• 不与以前画过的线重复。

构造一种包含 $k$ 条线的画法，把整个图覆盖。

显然构造题。

一种容易想到的方法是：我们使前 $k-1$ 条线每条经过两个点，最后一条线将剩余所有点连接。为了方便描述，我们以 $5\times 5$ 的网格图为例，对其进行编号：

假设 $k=4$，则四条线段分别经过如下点：

• $\operatorname{Line}1:(1,2)$
• $\operatorname{Line}2:(3,4)$
• $\operatorname{Line}3:(5,6)$
• $\operatorname{Line}4:(7,8,\cdots,25)$

基础思路有了，问题转化为如何根据点的编号求出其坐标。发现对于奇数行，编号正序；偶数行为倒序。我们根据这一特点对编号的行数进行分类，经过一定的数学推导，就可以得到行数和列数了。

pair<int, int> calcPos(int x) {
	int div = (x - 1) / n + 1, pos = (x - 1) % n + 1;
	if(div & 1) return make_pair(div, pos);
	return make_pair(div, n-pos+1);
}

然后根据上面说过的思路，计算出所有线的情况，输出即可。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
pair<int, int> calcPos(int x) {
	int div = (x - 1) / n + 1, pos = (x - 1) % n + 1;
	if(div & 1) return make_pair(div, pos);
	return make_pair(div, n-pos+1);
}

int main() {
	scanf("%d%d%d", &m, &n, &k);
	for(int i=1;i<k;i++) {
		printf("2 ");
		pair<int, int> _;
		_ = calcPos((i<<1)-1);
		printf("%d %d ", _.first, _.second);
		_ = calcPos(i<<1);
		printf("%d %d\n", _.first, _.second);
	}
	printf("%d ", n*m-((k-1)<<1));
	for(int i=(k<<1)-1;i<=n*m;i++) {
		pair<int, int> _;
		_ = calcPos(i);
		printf("%d %d ", _.first, _.second);
	}
	puts("");
	return 0;
}